Correlation is widely used in signal processing, to help to identify the presence of particular signal sequences. One form of correlation is described in the context of a radar system in U.S. Pat. No. 5,376,939, issued Dec. 27, 1994 in the name of Urkowitz.
Correlation processing is described generally by the equationRxy=∫X(n)Y(n−k)dn  (1)and discrete correlation can be represented by
                              R          yx                =                              ∑                          n              =              0                                      N              -              1                                ⁢                                          ⁢                                    X              ⁡                              (                n                )                                      ⁢                          Y              ⁡                              (                                  n                  -                  k                                )                                      ⁢                          ⅆ              n                                                          (        2        )            
Structure 10 of FIG. 1a illustrates a portion of a prior-art correlator structure which is well adapted to being fabricated on or in an Application-Specific Integrated Circuit (ASIC). ASICs are advantageous in that the desired structure can be selected and optimized in a relatively small integrated circuit. However, ASICs have long design and fabrication cycles, and can be expensive, especially if the number of units to be fabricated is small.
Structure 10 of FIG. 1a illustrates a portion of a correlator structure which is well adapted for fabrication on an ASIC. In FIG. 1a, a source 1 of first signal produces parallel signal, designated Y, and applies it by way of a path 1p to an input port 10i1 of a correlator illustrated as a block 10. A source 2 of second signal produces parallel signal on a path 2p for application to a second input port 10i2 of correlator block 10. Correlator 10 correlates the first signals Y with the second signals X and produces at its output port 10o a signal Rxy representing the correlation.
FIG. 1b illustrates details of one possible prior art embodiment of correlator 10 of FIG. 1a. In FIG. 1b, correlator 10 includes a clocked multibit register (R) which, at each cycle of a clock signal, gates or couples the bits of a first Y word onto a multibit bus 14. Correlator 10 also includes a set of multipliers (X) 160, 161, 162, . . . , 16N−1 of a set 16 of multipliers. Each multiplier of set 16 includes two input ports, one of which is a multibit input port, and one of which is a single-bit input port. More particularly, multiplier 160 includes a multibit input port 16i10, multiplier 161 includes a multibit input port 16i11, multiplier 162 includes a multibit input port 16i12, . . . , and multiplier 16N−1 includes a multibit input port 16i1N−1. The single-bit input ports of multipliers 160, 161, 162, . . . , 16N−1 are designated 16i20, 16i21, 16i22, . . . , 16i2N−1, respectively. All the bits of the Y word coupled onto bus 14 from register 12 are applied to the multibit first input ports of all the multipliers. That is, when a particular Y word appears on bus 14, all the bits of that Y word are applied to each of multibit input ports 16i10, 16i11, 16i12, . . . , and 16i1N−1. For each Y word coupled to the multibit input ports of set 16 of multipliers of FIG. 1b, the bits of a word are individually applied to the single-bit input ports 16i20, 16i21, 16i22, . . . , 16i2N−1 of multiplier set 16. The single-bit inputs can be viewed as being “control” bits which determine the state of the multiplier. In short, each multiplier 160, 161, 162, . . . , 16N−1 of set 16 multiplies the Y word applied to its multibit input port by either +1 or −1, depending upon the state of the “control” X bit applied to its single-bit input port. Thus, if the single X bit applied to input port 16i20 of multiplier 160 is a logic high (+1), the multibit Y word applied to its multibit input port 16i10 is translated without change by way of a multibit path 180 to an input port 20i10 of an adder 200, where it is added to any multibit word applied by way of a path 220 to an input port 20i20. As illustrated, the value of the word applied by way of a path 220 to input port 20i20 of adder 200 is zero. In a similar manner, the multibit Y word appearing on bus 14 is coupled simultaneously to first input ports 16i11, 16i12, . . . , and 16i1N−1 of the remaining multipliers 161, 162, . . . , 16N−1 of set 16, and each multiplier of set 16 multiplies the Y word by either +1 or −1 depending upon the state of the single bit of X input signal applied to the corresponding second input ports 16i20, 16i21, 16i22, . . . , 16i2N−1, and the resulting inverted or noninverted versions of the multibit Y signal or word are coupled to adders 200, 201, 202, . . . , 20N−1 of a set 20 of adders. Thus, the multiplied (that is, inverted or noninverted) multibit Y word from multiplier 160 is applied over path 180 to input port 20i10 of adder 200, the multiplied multibit Y word from multiplier 161 is applied over path 181 to input port 20i11 of adder 201, the multiplied multibit Y word from multiplier 162 is applied over path 182 to input port 20i12 of adder 202, . . . , and the multiplied multibit Y word from multiplier 16N−1 is applied over path 18N−1 to input port 20i1N−1 of adder 20N−1. Each adder 200, 201, 202, . . . , 20N−1 of set 20 of adders sums the multiplied multibit Y word (the addend) received from its associated multiplier 160, 161, 162, . . . , 16N−1 of set 16 of multipliers with or to the multibit number (the augend) applied to its second input port. Thus, the addend applied to input port 20i10 of adder 200 is summed with the augend applied to input port 20i20 of adder 200 to produce a sum which is applied to a register (R) 240 of a set of registers 24, the addend applied to input port 20i11 of adder 201 is summed with the augend applied to input port 20i21 of adder 201 to produce a sum which is applied to a register (R) 241, the addend applied to input port 20i12 of adder 202 is summed with the augend applied to input port 20i22 of adder 202 to produce a sum which is applied to a register (R) 242, . . . , and the addend applied to input port 20i1N−1 of adder 20N−1 is summed with the augend applied to input port 20i2N−1 of adder 20N−1 to produce a sum which is applied to a register (R) 24N−1. Each register 240, 241, 242, . . . , 24N−1 of set 24 of registers delays the coupling of the sum from the previous adder by one clock cycle. The correlation output appears at the output port 100 of register 24N−1.
In operation of the arrangement 10 of FIG. 1b, a new Y digital word is applied from register 12 to bus 14 at each clock cycle. At each clock cycle, the bits of a new X digital word are applied to the various bit input ports of multibit port or path 2p, and a multiplication occurs in the multipliers of set 16. The product is applied to the adders of set 20 and is added during the same clock cycle. This produces a sum at the output of each adder or summer of set 20 of adders. At the next clock cycle, the registers of set 20 each transfer the sum from its associated lower-numbered summer to the augend input port of the next higher-numbered adder. All registers are clocked at the same time. Parallel data Y changes on a clock-to-clock basis, but the X value does not change unless or until a different correlation is to be processed. All multiplications and additions occur on a clock-to-clock basis, and the intermediate results are stored in registers on a clock-to-clock basis. Hence the resultant output Rxy occurs on a clock-to-clock basis in a continuous stream until all Y values have been processed. On each clock cycle, the resultant output is the correlated output of Y to X, after the first initial N clocks. As an example if N is 8, it will take 8 clock cycles for valid correlated output to propagate to the resultant output. That is, correlated output appears at port 10o only after the first N clock cycles have passed.
In some computation-intensive applications, the words being processed may contain thousands of bits. Such large numbers of processing steps can be accommodated in a reasonable number of ASICs. However, in some contexts it may be desirable to use Field Programmable Gate Arrays (FPGAs) gate-programmable arrays instead of ASICs. Field Programmable Gate Arrays are advantageous in that they are commercially made in large numbers, and are both inexpensive and reliable. A disadvantage of Field Programmable Gate Arrays is that by nature each integrated circuit contains elements which are useful for the desired function, and also contains elements which may be less useful, or not at all useful. Consequently, more Field Programmable Gate Arrays FPGAs may be required, in order to perform correlations with words containing large numbers of bits, than is desirable for reasons of bulk and interconnection complexity.
Improved or alternative correlator arrangements are desired.